#include <iostream>
#include <queue>
#include <sstream>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Codec {
private:
    class read_util {
    private:
        string *str;
        int begin_index = 0;
        int length = 0;
        int ptr = 0;
    public:
        read_util(string& str) {
            this->str = &str;
        }

        string next() {
            if (ptr >= str->size()) {
                return "";
            }
            for (; ptr < str->size(); ptr++) {
                if ((str->at(ptr) >= '0' && str->at(ptr) <= '9') || (str->at(ptr) >= 'a' && str->at(ptr) <= 'z') || str->at(ptr) == '-') {
                    if (length == 0) {
                        begin_index = ptr;
                    }
                    length++;
                } else if (str->at(ptr) == ',' || str->at(ptr) == ']') {
                    string ans = str->substr(begin_index, length);
                    begin_index = ++ptr;
                    length = 0;
                    return ans;
                }
            }
            return "";
        }
    };
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == nullptr) {
            return "[]";
        }
        stringstream ans;
        ans << ("[" + to_string(root->val));
        bool end = root->left == nullptr && root->right == nullptr;
        queue<TreeNode*> queue;
        queue.push(root->left);
        queue.push(root->right);
        while (!end) {
            bool valid = false;
            for (int i = 0, len = queue.size(); i < len; i++) {
                TreeNode* node = queue.front();
                queue.pop();
                if (node == nullptr) {
                    ans << ",null";
                } else {
                    ans << "," + to_string(node->val);
                    if (node->left != nullptr || node->right != nullptr) {
                        valid = true;
                    }
                    queue.push(node->left);
                    queue.push(node->right);
                }
            }
            end = !valid;
        }
        ans << "]";
        string res;
        ans >> res;
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data == "[]") {
            return nullptr;
        }
        read_util read_util(data);
        string val = read_util.next();
        int val_i = atoi(val.data());
        queue<TreeNode*> queue;
        TreeNode* root = new TreeNode(val_i);
        queue.push(root);
        while (true) {
            TreeNode* node = queue.front();
            queue.pop();
            val = read_util.next();
            if (val == "null") {
            } else if (val == "") {
                break;
            } else {
                val_i = atoi(val.data());
                TreeNode* node1 = new TreeNode(val_i);
                node->left = node1;
                queue.push(node1);
            }
            val = read_util.next();
            if (val == "null") {
            } else if (val == "") {
                break;
            } else {
                val_i = atoi(val.data());
                TreeNode* node1 = new TreeNode(val_i);
                node->right = node1;
                queue.push(node1);
            }
        }
        return root;
    }
};


int main() {
    Codec codec;
    TreeNode t1(1), t2(2), t3(3), t4(4), t5(5), t6(6), t7(7);
    t1.left = &t2;
    t1.right = &t3;
    t3.left = &t4;
    t3.right = &t5;
    t5.left = &t6;
    t5.right = &t7;
    string output = codec.serialize(&t1);
    cout << output << endl;
    TreeNode* root = codec.deserialize(output);
    cout << endl;
}